// https://www.lintcode.com/problem/132-pattern/my-submissions

class Solution {
public:
    /**
     * @param nums: a list of n integers
     * @return: true if there is a 132 pattern or false
     */
    bool find132pattern(vector<int> &nums) {
        stack<int> s;
        int s2 = INT_MIN;
        for (int i = nums.size() - 1; i >= 0; --i)
        {
            if (nums[i] < s2)
                return true;
            else
            {
                while (!s.empty() && s.top() < nums[i])
                {
                    s2 = s.top();
                    s.pop();
                }
            }
            s.push(nums[i]);
        }
        return false;
    }
};